package PrefixSum2D;

import java.util.Arrays;

public class Main {

	// 构建二维前缀和数组
	public static int[][] buildPrefixSum(int[][] matrix) {
		int rows = matrix.length;
		int cols = matrix[0].length;
		
		//前缀和矩阵下标从1开始
		int[][] prefixSum = new int[rows + 1][cols + 1];

		for (int i = 1; i <= rows; i++) {
			for (int j = 1; j <= cols; j++) {
				prefixSum[i][j] = prefixSum[i - 1][j] + prefixSum[i][j - 1] - prefixSum[i - 1][j - 1]
						+ matrix[i - 1][j - 1];
			}
		}

		return prefixSum;
	}

	public static void main(String[] args) {
		int[][] matrix = { 
			{ 1, 2, 3 }, 
			{ 4, 5, 6 }, 
			{ 7, 8, 9 } 
		};

		// 构建前缀和数组
		int[][] prefixSum = buildPrefixSum(matrix);
		
		//输出前缀和数组
		for(int i=0;i<prefixSum.length;i++) {
			System.out.println(Arrays.toString(prefixSum[i]));
		}

	}

}
